package simple;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class Solution20 {
    public boolean isValid(String s) {
        //字符偶数才可能匹配
        int n = s.length();
        if(n % 2 == 1){
            return false;
        }

    //存入map，进行不同类型的比对
    Map<Character, Character> map = new HashMap<Character, Character>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
    
    //双端队列模拟栈
    Deque<Character> stack = new LinkedList<Character>();

    //常规应该先左括号，后右
    for(int i = 0;i < n;i++){
        char c = s.charAt(i);
        //先右
        if(map.containsKey(c)){
            //栈无元素\栈顶不匹配
            if(stack.isEmpty() || stack.peek() !=  map.get(c)){
                return false;
            }
            //右正常，弹出
            stack.pop();
        //左  
        } else {
            stack.push(c);
        } 
    }
    //栈空，true；非空，false
    return stack.isEmpty();
    }
}